package base.sort.separate;

import base.sort.IMutableSorter;
import java.util.Arrays;

/**
 * 分治策略下的归并排序
 */
public class MergeSort implements IMutableSorter {
    @Override
    public void sort(int[] A) {
        mergeSort(A, 0, A.length);
    }

    private void mergeSort(int[] A, int l, int r) {
        // 退出条件
        if (r-l <= 1 ) {
            return;
        }
        // 偏右的中间位置
        int mid = (l + r + 1)/2;
        mergeSort(A, l, mid);
        mergeSort(A, mid, r);

        merge(A, l, mid, r);
    }

    private void merge(int[] A, int l, int mid, int r) {
        int[] B = Arrays.copyOfRange(A, l, mid+1);
        // copyOfRange超出会补零
        int[] C = Arrays.copyOfRange(A, mid, r+1);

        // 哨兵-保证最后一个元素固定最大，确保不发生越界
        B[B.length-1] = C[C.length-1] = Integer.MAX_VALUE;
        
        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if (B[i] < C[j]) {
                A[k] = B[i++];
            } else {
                A[k] = C[j++];
            }
        }
    }
}
